package com.shm.leetcode;

import java.util.*;

/**
 * @author: shm
 * @dateTime: 2020/9/24 15:27
 * @description: 501. 二叉搜索树中的众数
 * 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
 * <p>
 * 假定 BST 有如下定义：
 * <p>
 * 结点左子树中所含结点的值小于等于当前结点的值
 * 结点右子树中所含结点的值大于等于当前结点的值
 * 左子树和右子树都是二叉搜索树
 * 例如：
 * 给定 BST [1,null,2,2],
 * <p>
 * 1
 * \
 * 2
 * /
 * 2
 * 返回[2].
 * <p>
 * 提示：如果众数超过1个，不需考虑输出顺序
 * <p>
 * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
 */

public class FindMode {
    List<Integer> list = new ArrayList<>();
    //表示当前节点的值
    int current = 0;
    //表示当前节点的数量
    int count = 0;
    //最大的重复数量
    int maxCount = 0;

    /**
     * @author: shm
     * @dateTime: 2020/9/24 16:01
     * @description: 我们都知道二叉搜索树的中序遍历是有序的，有一种方式就是把二叉搜索树中序遍历的结果存放到一个数组中，因为这个数组是升序的（虽然有重复的），我们可以遍历这个数组，这里使用几个变量
     * <p>
     * 使用变量curent表示当前的值，count表示当前值的数量，maxCount表示重复数字最大的数量。list集合存放结果
     * <p>
     * 1，如果节点值等于curent，count就加1，
     * <p>
     * 2，如果节点不等于current，说明遇到了下一个新的值，更新current为新的值，然后让count=1；
     * <p>
     * 接着比较count和maxCount的大小，
     * <p>
     * 如果count==maxCount，就把当前节点的值加入到集合list中。
     * 如果count>maxCount，先把list集合清空，然后再把当前节点的值加入到集合list中，最后在更新maxCount的值。
     * <p>
     * <p>
     * 如果先把树的节点找出来在计算有点麻烦，我们可以在遍历树的节点的时候就判断，这样就会好一些，下面使用两种方式，一种是递归的，一种是非递归的。树的中序遍历顺序如下
     * <p>
     * 左子节点→当前节点→右子节点
     * <p>
     * 作者：sdwwld
     * 链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/er-cha-shu-zhong-xu-bian-li-de-liang-chong-fang-sh/
     */
    public int[] findMode(TreeNode root) {
        inorderTraversal(root);
        int[] res = new int[list.size()];
        //把集合list转化为数组
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    //递归方式
    public void inorderTraversal(TreeNode root) {
        //终止条件判断
        if (root == null) {
            return;
        }
        //遍历左子树
        inorderTraversal(root.left);
        //下面是对当前节点的一些逻辑操作
        int value = root.val;
        if (value == current) {
            //如果节点值等于curent，count就加1
            count++;
        } else {
            //否则，就表示遇到了一个新的值，curent和count都要
            //重新赋值
            current = value;
            count = 1;
        }
        if (count == maxCount) {
            //如果count == maxCount，就把当前节点加入到集合中
            list.add(value);
        } else if (count > maxCount) {
            //否则，当前节点的值重复量是最多的，直接把list清空，然后
            //把当前节点的值加入到集合中
            list.clear();
            maxCount = count;
            list.add(value);
        }
        //遍历右子树
        inorderTraversal(root.right);
    }

    //非递归方式
    public void inorderTraversal_2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        Deque<TreeNode> deque = new LinkedList<>();
        while (root != null || !deque.isEmpty()) {
            while (root != null) {
                deque.push(root);
                root = root.left;
            }

            if (!deque.isEmpty()) {
                root = deque.pop();
                int value = root.val;
                if (value == current) {
                    count++;
                } else {
                    current = value;
                    count = 1;
                }

                if (count == maxCount) {
                    list.add(value);
                } else if (count > maxCount) {
                    list.clear();
                    list.add(value);
                    maxCount = count;
                }
                root = root.right;
            }
        }
    }
}
